package datastructure.book.tujiesuanfa.divideandconquer._1_all;

import datastructure.book.tujiesuanfa.tree.bean.Node;
import datastructure.book.tujiesuanfa.tree.bean.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution1 {
    /**
     * 根据二叉树的先序遍历结果 preorder 和 中序遍历结果inorder 构造出这棵二叉树并返回其根节点
     * preorder 和 inorder 中均不含重复数字
     */
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        return deduceTree0(0,preorder.length-1,new int[]{0},preorder,inorder);
    }

    private TreeNode deduceTree0(int left,int right,int[] index,int[] preorder, int[] inorder){
        if (index[0] > preorder.length-1){
            return null;
        }
        if (left > right){
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[index[0]]);
        int m = -1;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == preorder[index[0]]){
                m = i;
                break;
            }
        }
        index[0]++;
        treeNode.left = deduceTree0(left,m-1,index,preorder,inorder);
        treeNode.right = deduceTree0(m+1,right,index,preorder,inorder);
        return treeNode;
    }

    /**
     * 判断整数数组 postorder 是否为某一二叉搜索树的后序遍历结果
     * postorder 中无重复数字
     * 左子树中所有节点的值 < 根节点的值，右子树中所有节点的值>根节点的值；
     * 其左、右子树也分别为二叉搜索树
     * 例如 postorder = [4,9,6,5,8]  返回 false
     * 无法从该后序遍历结果构造出一颗二叉搜索树
     * postorder = [4,6,5,9,8]   返回 true，可构造如下二叉搜索树
     *          8
     *     5         9
     *  4     6
     */
    public boolean verifyTreeOrder(int[] postorder) {
        return verifyTreeOrder0(postorder,0,postorder.length-1);
    }

    private boolean verifyTreeOrder0(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        int index = -1;
        //i到index-1，为左子树均小于根节点
        for (int k = i; k < j; k++) {
            if (postorder[k] > postorder[j]) {
                index = k;
                break;
            }
        }
        //没有大于根节点的，全为左子树
        if (index == -1) {
            return verifyTreeOrder0(postorder,i,j-1);
        } else if (index == i){
            //没有小于根节点的，全为右子树
            //index到j-1，为右子树均大于根节点
            for (int k = index; k < j; k++) {
                if (postorder[k] < postorder[j]) {
                    return false;
                }
            }
            return verifyTreeOrder0(postorder,i,j-1);
        }
        //index到j-1，为右子树均大于根节点
        for (int k = index; k < j; k++) {
            if (postorder[k] < postorder[j]) {
                return false;
            }
        }
        return verifyTreeOrder0(postorder,i,index-1) && verifyTreeOrder0(postorder,index,j-1);
    }

    /**
     * 计算 x 的 n 次方（即，x^n）
     * -100.0 < x < 100.0
     * -2^31 <= n <= 2^31-1
     */
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        if (x == 1) {
            return 1;
        }
        if (x == -1) {
            return n%2 == 0? 1 : -1;
        }
        if (n < 0) {
            n*=-1;
            return 1/myPow0(x,n);
        } else {
            return myPow0(x,n);
        }
    }
    private double myPow0(double x, int n){
        if (n == 0){
            return 1;
        }
        if (n == 1){
            return x;
        }
        if (n == 2){
            return x*x;
        }
        if (n == 3){
            return x*x*x;
        }
        int i = n % 2;
        int i1 = n / 2;
        double result1 = myPow0(x,i1);
        if (i == 0){
            return result1*result1;
        }else {
            return result1*result1*x;
        }
    }

    /**
     * 按照数字从小到大的顺序返回一个整数数列，该数列从数字 1 开始，到最大的正整数 cnt 位数字结束
     * 例如：cnt = 1，返回1-9
     * cnt = 2，返回1-99
     */
    public int[] countNumbers(int cnt) {
        if (cnt == 0){
            return new int[0];
        }
        if (cnt == 1){
            return new int[]{1,2,3,4,5,6,7,8,9};
        }
        int n = 10;
        for (int i = 1; i < cnt; i++) {
            n*=10;
        }
        int[] result = new int[n-1];
        result[0] = 1;
        result[1] = 2;
        result[2] = 3;
        result[3] = 4;
        result[4] = 5;
        result[5] = 6;
        result[6] = 7;
        result[7] = 8;
        result[8] = 9;
        int m = 10;
        int k = 100;
        for (int i = 1; i < cnt; i++) {
            while (m < k){
                result[m-1] = m;
                for (int j = 1; j < 10; j++) {
                    int num = m + j;
                    result[num-1] = num;
                }
                m+=10;
            }
            k*=10;
        }
        return result;
    }

    /**
     * 返回stock最小的 cnt 个数字，返回 顺序不限
     * 例如   4,6,8,1,3,3,5,6
     * cnt = 2  最小的2个数为  1,3
     * 0 <= cnt <= stock.length <= 10000
     * 使用O(n)级别的时间复杂度
     */
    public int[] inventoryManagement(int[] stock, int cnt) {
        if (stock == null || stock.length == 0 || cnt == 0) {
            return new int[0];
        }
        int[] result = new int[cnt];
        if (cnt == stock.length) {
            System.arraycopy(stock,0,result,0,cnt);
            return result;
        }
        int left = 0;
        int right = stock.length-1;
        while (true) {
            int splitIndex = quickSort(stock,left,right);
            if (splitIndex < cnt) {
                left = splitIndex+1;
            } else if (splitIndex > cnt) {
                right = splitIndex - 1;
            } else {
                break;
            }
        }
        System.arraycopy(stock,0,result,0,cnt);
        return result;
    }

    private int quickSort(int[] arr,int left,int right){
        if (left == right) {
            return left;
        }
        int tempVal = arr[left];
        while (true) {
            while (right > left && arr[right] > tempVal) {
                right--;
            }
            if (right == left){
                arr[left] = tempVal;
                break;
            }
            arr[left] = arr[right];
            left++;
            while (right > left && arr[left] < tempVal) {
                left++;
            }
            if (right == left){
                arr[left] = tempVal;
                break;
            }
            arr[right] = arr[left];
            right--;
        }
        return left;
    }

    @Test
    public void testQuickSort(){
        int[] ints = {5, 4, 2, 3, 6, 7, 8, 1};
        System.out.println(quickSort(ints, 0, ints.length-1));
        System.out.println(Arrays.toString(ints));
    }

    @Test
    public void testReversePairs(){
        System.out.println(reversePairs(new int[]{7,5,6,4}));
    }

    public int reversePairs(int[] record) {
        if (record == null || record.length == 0) {
            return 0;
        }
        ArrayList<Integer> list = new ArrayList<>();
        int result = 0;
        list.add(record[0]);
        for (int i = 1; i < record.length; i++) {
            int index = insertIndex(list,record[i]);
            result += (list.size()-index);
            list.add(index,record[i]);
        }
        return result;
    }

    private int insertIndex(ArrayList<Integer> list, int num) {
        int i = 0;
        int j = list.size()-1;
        while (i <= j) {
            int mid = (i+j)/2;
            if (list.get(mid) <= num) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }
}
